# 完全背包问题(Unbounded Knapsack Problem)
# 区别于01背包, 在 完全背包问题 中，每个物品可以被选无限次。

"""题目:
给定一个背包的容量 W 和一组物品，每个物品有一个重量 w[i] 和一个价值 v[i]。每种物品可以选取无限次。请设计一个算法，计算背包可以装下的最大总价值。
"""
from leetcode import test_function as tf


def complete_knapsack_classic(w: int, weights: list[int], values: list[int]) -> int:
    """经典解法
    dp[i][j] 表示在前i种物品在背包容量为j时的最大容量.
    和01背包的经典解法非常相似, 区别也是重点在于不从dp[i-1]维度进行状态转移, 而是从当前dp[i]来进行状态转移
    因为物品可以重复选择, 如果当前商品i的性价比更高, 则可以多次选择:
    dp[i-1][j] 表示在没有物品i时的最大价值
    dp[i-1][j-w] + v 表示只能选择一次物品i时的最大价值
    dp[i][j-w] + v 表示可以多次选择物品i时的最大价值
    """
    n = len(weights)
    dp = [[0] * (w + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        wi, vi = weights[i - 1], values[i - 1]
        for j in range(1, w + 1):
            if weights[i - 1] > j:  # 容量为j的背包装不下当前物品
                dp[i][j] = dp[i - 1][j]
            else:  # 可以装下当前物品
                # 注意: 和01背包相比, 区别在于不从dp[i-1][j - weights[i-1]]转移
                dp[i][j] = max(dp[i - 1][j], dp[i][j - wi] + vi)
    return dp[n][w]


def complete_knapsack_opt(w: int, weights: list[int], values: list[int]) -> int:
    """
    完全背包问题区别于01背包的关键点在于遍历背包最大容量j时, 使用的是正序遍历:
    由于每个物品可以多次选择, 所以在二重dp中, dp[i][j]并不依赖于dp[i-1]的数据(dp[i-1]表示在未考虑物品i时候的状态, 即每个物品只考虑1次),
    而是用dp[i]的状态即可, 也就是每个物品可以多次拿取
    """
    dp = [0] * (w + 1)
    for idx, weight in enumerate(weights):
        for j in range(weight, w + 1):  # 注意, 这里是正序遍历
            dp[j] = max(dp[j], dp[j - weight] + values[idx])

    return dp[w]


if __name__ == '__main__':
    inp = [{"w": 10, "weights": [2, 3, 4, 5], "values": [3, 4, 7, 8]}, {"w": 10, "weights": [3], "values": [6]}, ]
    out = [17, 18]
    tf(complete_knapsack_classic, inp, out)
    tf(complete_knapsack_opt, inp, out)
